// 归并排序链表
var sortList = function (head) {
  if (head == null || head.next == null) return head;

  let [left, right] = split(head);
  let pointer = new ListNode(null);
  return merge(pointer, sortList(left), sortList(right));
};

function split(node) {
  let slow = node,
    fast = node;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let left = node;
  let right = slow.next;
  slow.next = null;
  return [left, right];
}

function merge(root, left, right) {
  let pointer = root;
  while (left != null || right != null) {
    if (left == null) {
      pointer.next = right;
      right = right.next;
    } else if (right == null) {
      pointer.next = left;
      left = left.next;
    } else {
      if (left.val < right.val) {
        pointer.next = left;
        left = left.next;
      } else {
        pointer.next = right;
        right = right.next;
      }
    }
    pointer = pointer.next;
  }
  return root.next;
}

var sortList = function (head) {
  return mergeSort(head);
};

function mergeSort(head) {
  if (head === null || head.next === null) return head;
  let mid = findMiddle(head);
  // 分裂成两个链表
  let temp = mid.next;
  mid.next = null;
  let left = head,
    right = temp;
  left = mergeSort(left);
  right = mergeSort(right);
  return mergeSortLists(left, right);
}

function findMiddle(head) {
  let fast = head;
  let slow = head;
  while (fast && fast.next && fast.next.next) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
}

function mergeSortLists(l1, l2) {
  let pre = new ListNode(-1);
  let cur = pre;
  while (l1 && l2) {
    if (l1.val < l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 || l2;
  return pre.next;
}
